package com.example.recursion;

/**
 * @Date 2022/7/9
 * @Created by Jonathan
 */
public class Queen {


    public static void main(String[] args) {
        int[] record = new int[8];
        System.out.println(process(record, 0, 8));

    }


    private static int process(int[] record, int i, int n) {
        if (i == n) {
            return 1;
        }
        int ret = 0;
        for (int j = 0; j < n; j++) {
            if (isValid(record, i, j)) {
                record[i] = j;
                ret += process(record, i + 1, n);
            }
        }
        return ret;
    }

    private static boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {
            // 表示同列或者在一个斜线上了
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }


    /**
     * 位运算优化
     *
     * @param limit
     * @param colLim
     * @param leftDiamLim
     * @param rightDimLim
     * @return
     */

    private static int process2(int limit, int colLim,
                                int leftDiamLim, int rightDimLim) {
        if (limit == colLim) {
            return 1;
        }
        int pos = limit & (~(colLim | leftDiamLim | rightDimLim));
        int mostRightOne = 0;
        int res = 0;
        while (pos != 0) {
            // 取出pos位置最右侧的1来，剩下的都是0
            mostRightOne = pos & (~pos + 1);
            pos = pos - mostRightOne;
            res += process2(limit, colLim | mostRightOne,
                    (leftDiamLim | mostRightOne) << 1,
                    (rightDimLim | mostRightOne) >> 1
            );
        }
        return res;
    }
}
